package cn.yza.算法.排序算法;

/** 计数排序
 *  能够解决一般的情况，但是它有一个缺陷，那就是存在空间浪费的问题。
 *
 * 比如一组数据{101,109,108,102,110,107,103}，其中最大值为110，
 * 按照基础版的思路，我们需要创建一个长度为111的计数数组，
 * 但是我们可以发现，它前面的[0,100]的空间完全浪费了
 *
 * @author Honglixi
 * @create 2021-12-05 21:33
 */
public class CountSort01 {

    public int[] countSort(int[] A) {
        // 找出数组A中的最大值
        int max = Integer.MIN_VALUE;
        for (int num : A) {
            max = Math.max(max, num);
        }
        // 初始化计数数组count
        int[] count = new int[max+1];
        // 对计数数组各元素赋值
        for (int num : A) {
            count[num]++;
        }
        // 创建结果数组
        int[] result = new int[A.length];
        // 创建结果数组的起始索引
        int index = 0;
        // 遍历计数数组，将计数数组的索引填充到结果数组中
        for (int i=0; i<count.length; i++) {
            while (count[i]>0) {
                result[index++] = i;
                count[i]--;
            }
        }
        // 返回结果数组
        return result;
    }
}
